package org.example.sort;

import java.util.Arrays;

//快速排序算法
public class QuickSort {
    public static void main(String[] args) {
        Integer[] arr = {10, 15, 97, 15, 64, 75, 0, 23, 78, 62, 197, 2};
        //快速排序
        sort(arr);
        //打印输出排序后的数组
        System.out.println(Arrays.toString(arr));
    }

    //将数组中的两个元素交换
    private static void exch(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //对数组内的元素进行快速排序
    public static void sort(Comparable[] arr) {
        //定义两个最小最大的索引
        int lo = 0, hi = arr.length - 1;
        //调用重写的sort方法
        sort(arr, lo, hi);
    }

    //对数组中从lo到hi的元素进行排序
    public static void sort(Comparable[] arr, int lo, int hi) {
        //安全性校验
        if (hi <= lo) {
            return;
        }
        //对数组中的lo到hi的元素进行分组
        int partition = partition(arr, lo, hi);
        //让左子组有序
        sort(arr, lo, partition - 1);
        //让右子组有序
        sort(arr, partition + 1, hi);
    }

    //对数组中lo到hi的元素进行分组返回分组元素的索引
    //返回的索引是位置变换后的索引，就是子组中该分界值的索引
    public static int partition(Comparable[] arr, int lo, int hi) {
        //确定分界值
        Comparable a = arr[lo];
        //定义两个指针分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left = lo + 1;
        int right = hi;
        //切分
        while (true) {
            //先从左往右扫描，找到比分界值大的元素停止
            while (left <= right && arr[left].compareTo(a) <= 0) {
                left++;
            }
            //再从右往左扫描，找到比分界值小的值停止
            while (left <= right && arr[right].compareTo(a) >= 0) {
                right--;
            }
            //如果left大于等于right结束切分，如果没有则交换两个元素
            if (left >= right) {
                break;
            }
            //交换两个指针所指向的元素
            exch(arr, left, right);
        }
        //交换分界值
        exch(arr, lo, right);
        //返回对应的分界值所对应的索引
        return right;
    }
}
